<!doctype html>
<html lang="zh-cn">
<head>

    <meta charset="utf-8">
    <meta name="generator" content="Hugo 0.57.2" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1">

    <title>红黑树学习 | The Sky of OtsWang</title>
    <meta property="og:title" content="红黑树学习 - The Sky of OtsWang">
    <meta property="og:type" content="article">
        
    <meta property="article:published_time" content="2019-06-04T16:40:30&#43;08:00">
        
        
    <meta property="article:modified_time" content="2019-12-19T09:55:00&#43;08:00">
        
    <meta name="Keywords" content="golang,go语言,otswang,java,博客,python">
    <meta name="description" content="红黑树学习">
        
    <meta name="author" content="OtsWang">
    <meta property="og:url" content="https://otswang.gitee.io/hugo/post/algorithm/red_black_tree/">
    <link rel="shortcut icon" href="/favicon.ico" type="image/x-icon">

    <link rel="stylesheet" href="/hugo/css/normalize.css">
    
        <link rel="stylesheet" href="/hugo/css/prism.css">
    
    <link rel="stylesheet" href="/hugo/css/style.css">
    <script type="text/javascript" src="//cdn.bootcss.com/jquery/3.2.1/jquery.min.js"></script>

    


    
    
</head>

<body>
<header id="header" class="clearfix">
    <div class="container">
        <div class="col-group">
            <div class="site-name ">
                
                    <a id="logo" href="https://otswang.gitee.io/hugo/">
                        The Sky of OtsWang
                    </a>
                
                <p class="description">擅长写HelloWorld的小小码农</p>
            </div>
            <div>
                <nav id="nav-menu" class="clearfix">
                    
                    
                    <a  href="https://otswang.gitee.io/hugo/" title="Home">Home</a>
                    
                    <a  href="https://otswang.gitee.io/hugo/tags/" title="Tags">Tags</a>
                    
                    <a  href="https://otswang.gitee.io/hugo/categories/" title="Categories">Categories</a>
                    
                    <a  href="https://otswang.gitee.io/hugo/archives/" title="Archives">Archives</a>
                    
                    <a  href="https://otswang.gitee.io/hugo/about/" title="About">About</a>
                    
                </nav>
            </div>
        </div>
    </div>
</header>


<div id="body">
    <div class="container">
        <div class="col-group">

            <div class="col-8" id="main">
                <div class="res-cons">
                    <article class="post">
                        <header>
                            <h1 class="post-title">红黑树学习</h1>
                        </header>
                        <date class="post-meta meta-date">
                            2019年6月4日
                        </date>
                        
                        <div class="post-meta">
                            <span>|</span>
                            
                                <span class="meta-category"><a href="https://otswang.gitee.io/hugo/categories/algorithm">Algorithm</a></span>
                            
                        </div>
                        
                        
                        
                        <div class="post-content">
                            <p>红黑树是一种自平衡的二叉查找树，其查找、增加、删除等操作都可以在O(logN)的时间内完成，java的TreeMap，HashMap,STL中的map均是对红黑树结构的实现。</p>

<h2 id="红黑树的性质">红黑树的性质</h2>

<p>红黑树，为保证树结构的自平衡，定义如下规则：</p>

<ol>
<li>节点是红色和黑色</li>
<li>根是黑色</li>
<li>所有叶子都是黑色（叶子是nil节点）</li>
<li>每个红色节点必须有两个黑色子节点，即每条路径上不允许有连续的红色节点</li>
<li>每条路径上黑色节点数目是一致的，黑等高</li>
</ol>

<ul>
<li>Every node is either red or black.</li>
<li>The root is black.</li>
<li>Every leaf (NIL) is black.</li>
<li>If a node is red, then both its children are black.</li>
<li>For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.</li>
</ul>

<p>性质4与5保证了任意节点到其每个叶子节点的路径最长不会超过最短路径的2倍。</p>

<h2 id="旋转操作">旋转操作</h2>

<p>左旋： 将某个节点旋转为右孩子的左孩子。 将右节点置为父节点。</p>

<p>右旋： 将某个节点旋转为左孩子的右孩子。 将左节点置为父节点。</p>

<p>图示：</p>

<p><img src="/hugo/src/img/algorithm/red_black_tree-左右旋.png" /></p>

<p>左旋步骤：</p>

<ol>
<li>当前节点的右孩子引用指向右孩子的左孩子；</li>
<li>将右孩子的左节点引用指向当前节点。</li>
</ol>

<p>右旋步骤：</p>

<ol>
<li>当前节点的左孩子引用指向左孩子的右孩子；</li>
<li>将左孩子的右孩子引用指向当前节点；</li>
</ol>

<h2 id="插入操作">插入操作</h2>

<p>性质1规定红黑树节点的颜色要么是红色要么是黑色，那么在插入新节点时，这个节点应该是红色还是黑色呢？答案是红色，如果插入的节点是黑色，那么这个节点所在路径比其他路径多出一个黑色节点，这个调整起来会比较麻烦（参考红黑树的删除操作，就知道为啥多一个或少一个黑色节点时，调整起来这么麻烦了）。如果插入的节点是红色，此时所有路径上的黑色节点数量不变，仅可能会出现两个连续的红色节点的情况。这种情况下，通过变色和旋转进行调整即可。</p>

<p><strong>情况1</strong></p>

<p>插入节点N为根节点时，节点N由红色变为黑色。</p>

<p><strong>情况2</strong></p>

<p>插入节点N的父节点为黑色时，不需要调整。</p>

<p><strong>情况3</strong></p>

<p>插入节点N的父节点是红色，叔叔节点也是红色。此时将父节点和叔叔节点变为黑色，此时条件5满足，但是需要注意的是如果父节点的父节点也是红色，需要递归调整。</p>

<p><strong>情况4</strong></p>

<p>N的父节点P为红色，叔叔节点为黑色，N是P的右孩子，父节点为P的左孩子，此时先对父节点P左旋，调整N与P的位置。</p>

<p><strong>情况5</strong></p>

<p>N的父节点P为红色，叔叔节点为黑色。N是P的左孩子，且P是父节点G的左孩子。此时对G右旋，并对P和G互换颜色。</p>

<p><strong>插入总结</strong></p>

<p><img src="/hugo/src/img/algorithm/insert.jpg" /></p>

<h2 id="删除操作">删除操作</h2>

<p>待学习</p>

<blockquote>
<p>参考资料 <a href="http://www.tianxiaobo.com/2018/01/11/%E7%BA%A2%E9%BB%91%E6%A0%91%E8%AF%A6%E7%BB%86%E5%88%86%E6%9E%90/">红黑树详细分析</a></p>
</blockquote>
                        </div>

                        


                        


                        <div class="post-meta meta-tags">
                            
                            <ul class="clearfix">
                                
                                <li><a href="https://otswang.gitee.io/hugo/tags/tree">Tree</a></li>
                                
                            </ul>
                            
                        </div>
                    </article>
                    
    

    
    
                </div>
            </div>
            <div id="secondary">

    <section class="widget">
        <form id="search" action="//www.google.com/search" method="get" accept-charset="utf-8" target="_blank" _lpchecked="1">
      
      <input type="text" name="q" maxlength="20" placeholder="Search">
      <input type="hidden" name="sitesearch" value="https://otswang.gitee.io/hugo/">
      <button type="submit" class="submit icon-search"></button>
</form>
    </section>

    
    <div class="clear">
        <div class="toc-article">
            <div class="toc-title">文章目录</dixsv>
            <nav id="TableOfContents">
<ul>
<li>
<ul>
<li><a href="#红黑树的性质">红黑树的性质</a></li>
<li><a href="#旋转操作">旋转操作</a></li>
<li><a href="#插入操作">插入操作</a></li>
<li><a href="#删除操作">删除操作</a></li>
</ul></li>
</ul>
</nav>
        </div>
    </div>
    

</div>
        </div>
    </div>
</div>
<footer id="footer">
    <div class="container">
        &copy; 2020 <a href="https://otswang.gitee.io/hugo/">The Sky of OtsWang By OtsWang</a>.
        Powered by <a rel="nofollow noreferer noopener" href="https://gohugo.io" target="_blank">Hugo</a>.
        <a href="https://www.flysnow.org/" target="_blank">Theme</a> based on <a href="https://github.com/Dudiao137/maupassant-hugo" target="_blank">maupassant-ots</a>.
        
    </div>
</footer>


    <script type="text/javascript">
    
    (function(){
        $("pre code").parent().addClass("line-numbers")
    }())

    window.MathJax = {
        tex2jax: {
            inlineMath: [ ['$','$'] ],
            processEscapes: true
        }
    };
    </script>
    <script type="text/javascript" src="/hugo/js/prism.js" async="true"></script>
    <script src='https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML' async></script>

<a id="rocket" href="#top"></a>
<script type="text/javascript" src="/hugo/js/totop.js?v=0.0.0" async=""></script>







 
 <script src="https://mermaidjs.github.io/scripts/mermaid.min.js"></script>
 <script>
       mermaid.initialize({ startOnLoad: true });
 </script>
</body>
</html>
